<html>
<head><meta charset="utf-8"><title>crates.io index · t-cargo/PubGrub · Zulip Chat Archive</title></head>
<h2>Stream: <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/index.html">t-cargo/PubGrub</a></h2>
<h3>Topic: <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/crates.2Eio.20index.html">crates.io index</a></h3>

<hr>

<base href="https://rust-lang.zulipchat.com">

<head><link href="https://rust-lang.github.io/zulip_archive/style.css" rel="stylesheet"></head>

<a name="217375377"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/crates.io%20index/near/217375377" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Matthieu Pizenberg <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/crates.2Eio.20index.html#217375377">(Nov 20 2020 at 08:57)</a>:</h4>
<p>Just had a quick look at zuse index, what are the meaning of the differents parts here for example?</p>
<div class="codehilite"><pre><span></span><code>cfg-if-wasm-bindgen-Minor(2)-&gt;=0.1.9, &lt;0.2.0/default
Links:openssl
</code></pre></div>



<a name="217381277"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/crates.io%20index/near/217381277" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Matthieu Pizenberg <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/crates.2Eio.20index.html#217381277">(Nov 20 2020 at 10:03)</a>:</h4>
<p>I think the way I'd go about dealing with crates, is I'd not use <code>OfflineDependencyProvider</code> with all cargo features embedded as data (encoded in package names that are all stored). I'd rather create a new <code>OfflineCrateProvider</code> similar to <code>OfflineDependencyProvider</code> but with cargo features embedded as logic.</p>
<p>I don't know how you deal with everything but concretely, for features for example I'd do something like this:</p>
<div class="codehilite" data-code-language="Rust"><pre><span></span><code><span class="k">type</span> <span class="nc">Index</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">Map</span><span class="o">&lt;</span><span class="n">Crate</span><span class="p">,</span><span class="w"> </span><span class="n">Map</span><span class="o">&lt;</span><span class="n">V</span><span class="p">,</span><span class="w"> </span><span class="n">CrateDeps</span><span class="o">&gt;&gt;</span><span class="p">;</span><span class="w"></span>

<span class="k">type</span> <span class="nc">CrateDeps</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">Map</span><span class="o">&lt;</span><span class="n">Feature</span><span class="p">,</span><span class="w"> </span><span class="n">Deps</span><span class="o">&gt;</span><span class="p">;</span><span class="w"></span>
<span class="k">type</span> <span class="nc">Feature</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="nb">String</span><span class="p">;</span><span class="w"></span>
<span class="k">type</span> <span class="nc">Deps</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">Map</span><span class="o">&lt;</span><span class="n">Crate</span><span class="p">,</span><span class="w"> </span><span class="n">Dep</span><span class="o">&gt;</span><span class="p">;</span><span class="w"></span>
<span class="k">type</span> <span class="nc">Crate</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="nb">String</span><span class="p">;</span><span class="w"></span>
<span class="k">type</span> <span class="nc">Dep</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="p">(</span><span class="n">Range</span><span class="o">&lt;</span><span class="n">V</span><span class="o">&gt;</span><span class="p">,</span><span class="w"> </span><span class="n">Set</span><span class="o">&lt;</span><span class="n">Feature</span><span class="o">&gt;</span><span class="p">);</span><span class="w"></span>

<span class="c1">// the id P would be a string uniquely identifying</span>
<span class="c1">// the crate with its activated features.</span>
<span class="n">to_crate_id</span><span class="w"> </span>: <span class="p">(</span><span class="n">Crate</span><span class="p">,</span><span class="w"> </span><span class="n">Set</span><span class="o">&lt;</span><span class="n">Feature</span><span class="o">&gt;</span><span class="p">)</span><span class="w"> </span>-&gt; <span class="nc">P</span><span class="p">;</span><span class="w"></span>
<span class="n">from_crate_id</span><span class="w"> </span>: <span class="nc">P</span><span class="w"> </span>-&gt; <span class="p">(</span><span class="n">Crate</span><span class="p">,</span><span class="w"> </span><span class="n">Set</span><span class="o">&lt;</span><span class="n">Feature</span><span class="o">&gt;</span><span class="p">);</span><span class="w"></span>

<span class="c1">// internally uses from_crate_id and to_crate_id.</span>
<span class="n">get_dependencies</span><span class="w"> </span>: <span class="p">(</span><span class="n">P</span><span class="p">,</span><span class="w"> </span><span class="n">V</span><span class="p">)</span><span class="w"> </span>-&gt; <span class="p">[(</span><span class="n">P</span><span class="p">,</span><span class="w"> </span><span class="n">Range</span><span class="o">&lt;</span><span class="n">V</span><span class="o">&gt;</span><span class="p">)]</span><span class="w"></span>
</code></pre></div>



<a name="217386199"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/crates.io%20index/near/217386199" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Eh2406 <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/crates.2Eio.20index.html#217386199">(Nov 20 2020 at 10:53)</a>:</h4>
<p>I do have a Dependency provider that is used to generate this. I look forward to polishing it up so I can share it and we can find ways to improve it. I don't want to have this several hundred line program in our test suite. One of the things it can do is turn each type safe <code>P</code> into a unique string. That lets our test suite only need to know how to read <code>OfflineDependencyProvider</code>.</p>



<a name="217386270"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/crates.io%20index/near/217386270" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Eh2406 <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/crates.2Eio.20index.html#217386270">(Nov 20 2020 at 10:54)</a>:</h4>
<p>(and no I don't know what I am doing up at this time.)</p>



<a name="217386412"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/crates.io%20index/near/217386412" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Eh2406 <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/crates.2Eio.20index.html#217386412">(Nov 20 2020 at 10:55)</a>:</h4>
<p><code>Links:openssl</code> There can only be one thing that links to a clib, or the linker gets mad, so <code>Links:openssl</code> means that that crate will link to <code>openssl</code> and so nothing else can.</p>



<a name="217387643"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/crates.io%20index/near/217387643" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Eh2406 <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/crates.2Eio.20index.html#217387643">(Nov 20 2020 at 11:08)</a>:</h4>
<p><code>cfg-if-wasm-bindgen-Minor(2)-&gt;=0.1.9, &lt;0.2.0/default</code> this is a lot to unpack.<br>
<code>/default</code> means that whatever we select we need to enable the <code>default</code> set of features.<br>
<code>bindgen-Minor(2)</code> means a the crate <code>bindgen</code> but only if it is <code>0.2.x</code>. We need that info in the package name as we can also have a <code>0.1.x</code> and a <code>1.x.y</code> in the same resolution.<br>
<code>cfg-if ... -&gt;=0.1.9, &lt;0.2.0</code> means that we depend on <code>cfg-if</code>in the range <code>&gt;=0.1.9, &lt;0.2.0</code> in this case that is the same as <code>cfg-if-Minor(1)</code>, but if it was the range <code>&gt;=0.1.9, &lt;0.3.0</code>then it would let us pick between  <code>cfg-if-Minor(1)</code> and <code>cfg-if-Minor(2)</code>. We can have different versions selected for different parents. <br>
So all together it is:<br>
<code>bindgen-Minor(2)</code> depends on <code>cfg-if ... -&gt;=0.1.9, &lt;0.2.0</code> (even if that spans incompatible versions) and needs the <code>default</code> set of features.</p>



<a name="217400350"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/crates.io%20index/near/217400350" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Matthieu Pizenberg <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/crates.2Eio.20index.html#217400350">(Nov 20 2020 at 13:29)</a>:</h4>
<p>I must admit I am lost ahah</p>



<a name="217401921"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/crates.io%20index/near/217401921" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Alex Tokarev <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/crates.2Eio.20index.html#217401921">(Nov 20 2020 at 13:42)</a>:</h4>
<p>That's because all the things we haven't implemented for Cargo specifically are encoded in this format</p>



<a name="217402023"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/crates.io%20index/near/217402023" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Alex Tokarev <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/crates.2Eio.20index.html#217402023">(Nov 20 2020 at 13:43)</a>:</h4>
<p>Multiple major versions are allowed, features can be enabled, and "links" attributes are in there as well</p>



<a name="217402241"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/crates.io%20index/near/217402241" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Alex Tokarev <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/crates.2Eio.20index.html#217402241">(Nov 20 2020 at 13:45)</a>:</h4>
<p>0.2 has additional dependency on <code>wasm-bindgen</code>, while 0.1 does not, so it's encoded in the name too</p>



<a name="217406029"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/crates.io%20index/near/217406029" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Eh2406 <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/crates.2Eio.20index.html#217406029">(Nov 20 2020 at 14:18)</a>:</h4>
<p>So 3 lessons from this try:</p>
<ul>
<li>it can run for all crates in the index if one lets it run overnight. Runtime is over 4h and the file is 207MB.</li>
<li>the names that get assigned for the complicated interacting hacks need to be improved, as you found them confusing.</li>
<li>I need to not try to describe things when I am randomly up in the middle of the night, as it does not make things clearer.</li>
</ul>



<a name="217408270"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/crates.io%20index/near/217408270" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Eh2406 <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/crates.2Eio.20index.html#217408270">(Nov 20 2020 at 14:37)</a>:</h4>
<p>Let's say for argument purposes my current code is:</p>
<ul>
<li>incorrect, in that it does not exactly incode the rules that Cargo would use.</li>
<li>overly complicated, in that is makse more complex examples then it needs to. (Reading my ramblings from last night, I think this one is true.)</li>
<li>inefficient, in that it does not use Pubgrub the best way for the complexity it needs.</li>
</ul>
<p>It is still an interesting benchmark on it own with a very high Time/MB, and a realistic example in that it code that someone new to using PubGrub actually wrote.</p>



<a name="217408528"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/crates.io%20index/near/217408528" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Eh2406 <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/crates.2Eio.20index.html#217408528">(Nov 20 2020 at 14:39)</a>:</h4>
<p>I.E. we have to goles 1 figure out what is needed for Cargo, 2 benchmark PubGrub.<br>
It still can work for 2 even if it is a WIP for 1.</p>



<a name="217413439"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/crates.io%20index/near/217413439" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Matthieu Pizenberg <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/crates.2Eio.20index.html#217413439">(Nov 20 2020 at 15:16)</a>:</h4>
<p>"It depends". For example, the ratio of valid / invalid dependencies is a lot lower for one thing.</p>
<div class="codehilite"><pre><span></span><code>solutions: 1909
errors: 279
</code></pre></div>
<p>And the code that builds the derivation tree has not been optimized at all, so that may be part of the problem.</p>
<p>Another thing to factor is is that if 1 package is very long to build, it's usually also because it's dependencies are very long to build. So when building a benchmark that iterates over all packages of a single very long to build package, it's normal to end up with hight time/mb</p>



<a name="217419921"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/crates.io%20index/near/217419921" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Matthieu Pizenberg <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/crates.2Eio.20index.html#217419921">(Nov 20 2020 at 16:01)</a>:</h4>
<blockquote>
<p>And the code that builds the derivation tree has not been optimized at all, so that may be part of the problem</p>
</blockquote>
<p>I'll agree though that it's a good benchmark to optimize the code building the data structure used for error reporting (currently called <code>DerivationTree</code>) :)</p>



<a name="217424122"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/crates.io%20index/near/217424122" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Eh2406 <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/crates.2Eio.20index.html#217424122">(Nov 20 2020 at 16:29)</a>:</h4>
<blockquote>
<p>Another thing to factor is is that if 1 package is very long to build, it's usually also because it's dependencies are very long to build.</p>
</blockquote>
<p><a href="https://github.com/mpizenberg/pubgrub-rs/issues/16">pubgrub#16</a> links to <a href="https://github.com/rust-lang/cargo/issues/8539#issuecomment-671074837">https://github.com/rust-lang/cargo/issues/8539#issuecomment-671074837</a> witch is a case (with <code>-Zminimal-versions</code>) where either of <code>self_update = "*"</code> and <code>solana-metrics = "*"</code> solve instantly but both takes over 50 min. So the really interesting slow cases do not have the shape you described, but most slow cases do have that shape. And your point still stands, "build all" has <code>O(n^2)</code> even without pathologies.</p>



<a name="217431354"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/crates.io%20index/near/217431354" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Matthieu Pizenberg <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/crates.2Eio.20index.html#217431354">(Nov 20 2020 at 17:16)</a>:</h4>
<p><span class="user-mention" data-user-id="120179">@Eh2406</span> I just tried using crates_index and cant figure out how to make it work. The example in the docs (<a href="https://docs.rs/crates-index/0.16.2/crates_index/index.html">https://docs.rs/crates-index/0.16.2/crates_index/index.html</a>) gives an empty iterator it seems. Any idea of what might go wrong?</p>



<a name="217432303"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/crates.io%20index/near/217432303" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Matthieu Pizenberg <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/crates.2Eio.20index.html#217432303">(Nov 20 2020 at 17:23)</a>:</h4>
<p>Ok actually, the problem seems to be linked to <code>new_cargo_default()</code>, if I use this, it does not figure out how to load the index used by cargo itself. Weird. If I change the path by using something like <code>new("_index")</code> it works.</p>



<a name="217438363"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/crates.io%20index/near/217438363" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Matthieu Pizenberg <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/crates.2Eio.20index.html#217438363">(Nov 20 2020 at 18:10)</a>:</h4>
<p>Are "build" dependencies of your dependencies necessary to <code>cargo build</code> your own crate?</p>



<a name="217449216"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/crates.io%20index/near/217449216" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Eh2406 <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/crates.2Eio.20index.html#217449216">(Nov 20 2020 at 19:39)</a>:</h4>
<p>"build" dependencies are "dev" dependencies are not. Sorry I have not had time to work on my script today. I will hopefully get it in shape to share tomorrow.</p>



<a name="217465700"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/crates.io%20index/near/217465700" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Matthieu Pizenberg <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/crates.2Eio.20index.html#217465700">(Nov 20 2020 at 22:15)</a>:</h4>
<p>no worry I was just trying few things and wanted to understand those details. I've never used build dependencies in rust yet</p>



<a name="217497507"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/crates.io%20index/near/217497507" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Matthieu Pizenberg <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/crates.2Eio.20index.html#217497507">(Nov 21 2020 at 11:20)</a>:</h4>
<p><span class="user-mention" data-user-id="120179">@Eh2406</span> to parse the versions requirements did you use the semver crate? It does not seem possible to extract the different segments of a <code>VersionReq</code> with the public API. Did you copy-pasted the code and added conversion functions to range? (or maybe just rolled you own parser)<br>
I see there can be multiple requirements separated by a comma in the dependencies of cargo toml. I've even seen one with 2 commas:</p>
<div class="codehilite"><pre><span></span><code>&lt;0.3, &gt;=0.1, &gt;=0.2.0-beta.0
</code></pre></div>



<a name="217517317"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/crates.io%20index/near/217517317" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Eh2406 <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/crates.2Eio.20index.html#217517317">(Nov 21 2020 at 20:23)</a>:</h4>
<p>Lost some time to a headache today. I will follow up with this when I am feeling better. <br>
Ya the semver crate is a odd beest. What I did was keep a list <code>(semver::Version, pubgrub::Semver)</code>. Then I can filter using  <code>VersionReq.matches(Version)</code>. Then I can make a <code>Range::between(min, max)</code>. It is a hack but it works.</p>



<a name="217517398"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/crates.io%20index/near/217517398" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Matthieu Pizenberg <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/crates.2Eio.20index.html#217517398">(Nov 21 2020 at 20:25)</a>:</h4>
<p>Don't worry about it, I did something forking the crate. Currently WIP but I'll say more soon</p>



<a name="217517471"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/crates.io%20index/near/217517471" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Eh2406 <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/crates.2Eio.20index.html#217517471">(Nov 21 2020 at 20:26)</a>:</h4>
<p>I look forward to comparing our aproteches!</p>



<a name="217527446"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/crates.io%20index/near/217527446" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Matthieu Pizenberg <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/crates.2Eio.20index.html#217527446">(Nov 22 2020 at 01:01)</a>:</h4>
<p>Alright, I've pushed my work to the "crates" branch. You should read the example <code>examples/crates/main.rs</code>.<br>
First comment the line written <code>// THEN DO THIS</code>, and uncomment the line <code>// DO THIS FIRST</code> and run</p>
<div class="codehilite"><pre><span></span><code>cargo run --release --features=serde --example crates
</code></pre></div>
<p>It will create the ron file in <code>temp/index.ron</code>.<br>
This files is the serialization of my adaptation of the index, which store features in a rather efficient way.<br>
Then you can toggle the commenting you just did on <code>examples/crates/main.rs</code> and re-run the examples. It will try to solve dependencies of all packages (with only mandatory dependencies). At the time of downloading the index for me, there was 51673 crates, 313123 unique versions, 301536 not yanked ones. From this, I build my index with only crates that do not specify specific targets (like windows and such) and only normal versions (not pre-release) so the index is down to 280906 versions.</p>
<p>From that index of 280906 versions, I solve dependencies of all of these with mandatory dependencies. The resolution was successful for 216794 of those 280906 versions and took 4 minutes on my computer.</p>



<a name="217531795"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/crates.io%20index/near/217531795" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Eh2406 <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/crates.2Eio.20index.html#217531795">(Nov 22 2020 at 03:22)</a>:</h4>
<p>This is a great start! Thank you for sharing! Eventually I think this should probably live in <a href="https://github.com/pubgrub-rs/advanced_dependency_providers">https://github.com/pubgrub-rs/advanced_dependency_providers</a>. But we can figure that out later. I have three thoughts/things to work on next:</p>
<ol>
<li>Cargo's resolver ( for now ) always includes target-specific dependencies, that field gets used later in the pipeline. So it is more accurate and less code to keep them in. On the other hand <code>dev</code> dependencies can be completely ignored, there is some debate but it may just be a bug that we add them to the index.</li>
<li>I think having features trigger there optional dependencies, is going to make solving the ron file significantly more complicated.</li>
<li>Another source of complexity is one-per-mager. let's say we have: </li>
</ol>
<div class="codehilite"><pre><span></span><code>a:
  1.0
 1.1
 2.0
 2.1
b:
  1.0 -&gt; a=&quot;&lt;=1.1&quot;
c:
  1.0 -&gt; a=&quot;&gt;=2.1&quot;
d:
  1.0 -&gt; a=&quot;&gt;=1.1,&lt;=2.0&quot;
e:
  1.0 -&gt; b=&quot;*&quot; c=&quot;*&quot; d=&quot;*&quot;
</code></pre></div>
<p>Cargo thinks the set <code>{e:1.0, d:1.0, c:1.0,b:1.0, a:1.1, a:2.1  }</code> is a valid solution, I don't think this code handels that yet.<br>
Making sure that that 2 and 3 work well together adds yet more complexity.<br>
But this is a great start and definitely better organized then my code.</p>



<a name="217547282"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/crates.io%20index/near/217547282" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Matthieu Pizenberg <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/crates.2Eio.20index.html#217547282">(Nov 22 2020 at 11:37)</a>:</h4>
<blockquote>
<p>I think having features trigger there optional dependencies, is going to make solving the ron file significantly more complicated</p>
</blockquote>
<p>I don't think so. With that design everything is ready already to include features. There is just two places to modify. First in complete the <code>featured_from</code> function like <code>mandatory_from</code> (<a href="https://github.com/pubgrub-rs/pubgrub/blob/crates/examples/crates/index.rs#L96">https://github.com/pubgrub-rs/pubgrub/blob/crates/examples/crates/index.rs#L96</a>). Second is extending the dependencies returned by <code>get_dependencies</code> here <a href="https://github.com/pubgrub-rs/pubgrub/blob/crates/examples/crates/index.rs#L207">https://github.com/pubgrub-rs/pubgrub/blob/crates/examples/crates/index.rs#L207</a>. Both are rather straightforward but I did not need it to make this PoC.</p>
<p>It may take a bit longer and the ron file might be a bit bigger but I don't think it will change a lot.</p>



<a name="217547347"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/crates.io%20index/near/217547347" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Matthieu Pizenberg <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/crates.2Eio.20index.html#217547347">(Nov 22 2020 at 11:39)</a>:</h4>
<blockquote>
<p>Another source of complexity is one-per-mager</p>
</blockquote>
<p>That was indeed not included in this PoC. I think it should be studied on its own to find a good solution, in isolation to all other additional complexity like features and such.</p>



<a name="217555814"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/crates.io%20index/near/217555814" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Eh2406 <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/crates.2Eio.20index.html#217555814">(Nov 22 2020 at 15:14)</a>:</h4>
<p>Looking again in the morning is there something that makes sure that <code>a:feat1</code> and <code>a:feat2</code> get the same version?</p>



<a name="217555955"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/crates.io%20index/near/217555955" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Eh2406 <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/crates.2Eio.20index.html#217555955">(Nov 22 2020 at 15:19)</a>:</h4>
<p>Most of the complexity of <code>cfg-if-wasm-bindgen-Minor(2)-&gt;=0.1.9, &lt;0.2.0/default</code> comes from the intersection of one-per-mager and feature related dependencies. There are a number of good encodings of features. There is at least one good encoding of one-per-mager. But when you put them together there is more complexity than the sum of the parts.</p>



<a name="217556625"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/crates.io%20index/near/217556625" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Matthieu Pizenberg <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/crates.2Eio.20index.html#217556625">(Nov 22 2020 at 15:39)</a>:</h4>
<blockquote>
<p>Looking again in the morning is there something that makes sure that a:feat1 and a:feat2 get the same version?</p>
</blockquote>
<p>You're right I didn't encode this. I think you mentioned a possible elegant solution to this in our past discussions. <code>get_dependencies</code> for <code>a:feat1</code> at version v1 could return the <code>feat1</code> dependencies of v1 plus a dependency to a raw <code>a</code> at v1. In turn <code>get_dependencies</code> for <code>a</code> would return mandatory dependencies of a. As such every feature such as <code>a:featN @ v</code> would have an exact dependency to <code>a @ v</code>. This will force selection of the same version.</p>



<a name="217556707"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/crates.io%20index/near/217556707" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Eh2406 <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/crates.2Eio.20index.html#217556707">(Nov 22 2020 at 15:41)</a>:</h4>
<p>Sounds like a plan, just wanted to be sure your encoding did not mean there was a more elegant solution that I had missed when reading the code.</p>



<a name="217556766"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/crates.io%20index/near/217556766" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Matthieu Pizenberg <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/crates.2Eio.20index.html#217556766">(Nov 22 2020 at 15:42)</a>:</h4>
<blockquote>
<p>when you put them together there is more complexity than the sum of the parts</p>
</blockquote>
<p>Right again. I still think it would be very useful to find a clean solution for the "multiple-versions" problem first, before trying to find a solution to the combined problem. At least because it's nice problem on its own.  It also maybe corresponds to the behavior of some registries (NPM works like that right?)</p>



<a name="217556843"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/crates.io%20index/near/217556843" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Matthieu Pizenberg <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/crates.2Eio.20index.html#217556843">(Nov 22 2020 at 15:44)</a>:</h4>
<p>I'm trying to put on paper some thoughts, will see if something useful come out of this</p>



<a name="217556925"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/crates.io%20index/near/217556925" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Matthieu Pizenberg <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/crates.2Eio.20index.html#217556925">(Nov 22 2020 at 15:46)</a>:</h4>
<p>Question related to the "multiple versions" case. If a depends on d1, b depends on d2 and c depends on d1 or d2, do you know what is done for c?</p>



<a name="217556998"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/crates.io%20index/near/217556998" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Eh2406 <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/crates.2Eio.20index.html#217556998">(Nov 22 2020 at 15:48)</a>:</h4>
<p>It will get the highest one that works with the other requirements. See my example from last night.</p>



<a name="217557237"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/crates.io%20index/near/217557237" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Eh2406 <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/crates.2Eio.20index.html#217557237">(Nov 22 2020 at 15:54)</a>:</h4>
<p>One solution to "multiple versions" on its own. (The one I have been working with.)<br>
So a semver req like <code>&gt;=2.0, &lt; 4.0</code> can be expressed as <code>Range::between(2.0, 3.0) Or Range::between(3.0, 4.0)</code>. We already have a way to express <code>Or</code>. <code>Or</code> is just multiple versions of a package. So we change req like <code>&gt;=2.0, &lt; 4.0</code>into a new package with two versions one depends on <code>Range::between(2.0, 3.0)</code> and the other depends on <code>Range::between(3.0, 4.0)</code>.</p>



<a name="217557392"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/crates.io%20index/near/217557392" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Eh2406 <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/crates.2Eio.20index.html#217557392">(Nov 22 2020 at 15:58)</a>:</h4>
<p>So what do we do with <code>&gt;=2.0, &lt; 999.0</code>are we going to make a package with 997 versions? We could but it wouldn't be efficient. What we can do is look at the versions that are actually available and only add the relevant versions.</p>



<a name="217557542"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/crates.io%20index/near/217557542" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Matthieu Pizenberg <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/crates.2Eio.20index.html#217557542">(Nov 22 2020 at 16:02)</a>:</h4>
<p>So if I call [2, 3[ or [3, 4[ a "bucket" ([0.1, 0.2[ would also be a bucket) you create one version per existing bucket.</p>



<a name="217557579"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/crates.io%20index/near/217557579" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Matthieu Pizenberg <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/crates.2Eio.20index.html#217557579">(Nov 22 2020 at 16:03)</a>:</h4>
<p>And an issue is that it grows in n2 with the number of dependencies that would require multiple buckets right?</p>



<a name="217557639"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/crates.io%20index/near/217557639" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Eh2406 <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/crates.2Eio.20index.html#217557639">(Nov 22 2020 at 16:04)</a>:</h4>
<p>Now we need to tell it that the buckets are compatible. So we add it to the name. <code>serde-major(1)</code> is the name for <code>serde</code> <code>Range::between(1.0, 2.0)</code>.</p>



<a name="217557667"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/crates.io%20index/near/217557667" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Eh2406 <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/crates.2Eio.20index.html#217557667">(Nov 22 2020 at 16:05)</a>:</h4>
<blockquote>
<p>And an issue is that it grows in n2 with the number of dependencies that would require multiple buckets right?</p>
</blockquote>
<p>I don't think I see your point, can you elaborate?</p>



<a name="217557723"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/crates.io%20index/near/217557723" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Matthieu Pizenberg <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/crates.2Eio.20index.html#217557723">(Nov 22 2020 at 16:06)</a>:</h4>
<p>nah not clear enought for me, I thought I had something and then it vanished from my mind ahah</p>



<a name="217557735"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/crates.io%20index/near/217557735" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Eh2406 <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/crates.2Eio.20index.html#217557735">(Nov 22 2020 at 16:06)</a>:</h4>
<p>That happens a lot to me.</p>



<a name="217557747"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/crates.io%20index/near/217557747" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Matthieu Pizenberg <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/crates.2Eio.20index.html#217557747">(Nov 22 2020 at 16:07)</a>:</h4>
<p>I mean I've to think a little more, but I'll make a cookie pause now ^^</p>



<a name="217557842"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/crates.io%20index/near/217557842" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Eh2406 <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/crates.2Eio.20index.html#217557842">(Nov 22 2020 at 16:10)</a>:</h4>
<p>In theory we could notice in advance that <code>&gt;=2.0, &lt; 3.0</code> will only have one bucket, and skip an indirection , but the code complexity has not been worth it so far.</p>



<a name="217566268"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/crates.io%20index/near/217566268" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Eh2406 <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/crates.2Eio.20index.html#217566268">(Nov 22 2020 at 19:38)</a>:</h4>
<p>I pushed a copy of what I've bean making: <a href="https://github.com/pubgrub-rs/pubgrub/compare/dev...crates2">https://github.com/pubgrub-rs/pubgrub/compare/dev...crates2</a><br>
It is repetitive and has bad naming, but if you feel like taking a look, there it is.</p>



<a name="217575158"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/crates.io%20index/near/217575158" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Matthieu Pizenberg <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/crates.2Eio.20index.html#217575158">(Nov 22 2020 at 23:05)</a>:</h4>
<p>I will certainly take a look during the week. I've also tried to formalize your "multiple-versions" method combined with my "on-the-file" packages id generators for an implementation of a dynamic "multiple-versions" dependency provider. Here is the explanation, let me know if you think this is clear.</p>
<hr>
<p>For every package, we pre-compute "buckets", which are intervals in which<br>
there can only be 1 version picked. So for example, if existing versions are<br>
(0.1.0, 0.1.1, 0.2.0, 1.0.0, 1.0.1, 3.3.0), there are 4 buckets which are<br>
{0.1.0, 0.1.1},  {0.2.0},  {1.0.0, 1.0.1},  {3.3.0}.<br>
The rules of semantic versioning mean that before version 1.0.0, a bucket corresponds to<br>
a minor version, and after it, a bucket corresponds to a major version.<br>
But in general, buckets can be anything as long as it means for the implementer<br>
that only 1 version per bucket can be selected.<br>
With semantic versioning, we can easily identify buckets<br>
by the first version of the corresponding bucket range.<br>
So the bucket identifier of the range [0.1.0, 0.2.0[ is 0.1.0 while<br>
the bucket identifier of the range [2.0.0, 3.0.0[ is 2.0.0</p>
<p>If "p" @ v depends on "q" in range r, the base idea of bucketted dependency resolver is:</p>
<ul>
<li>
<p>One version of imaginary package "p@v#q" per existing bucket of "q"<br>
    with a non-nul intersection with r.<br>
    That version is the bucket identifier.</p>
</li>
<li>
<p>Each version of "p@v#q" depends on "q$b" @ s where<br>
    b is the version identifier of the current bucket and<br>
    s is the intersection of the range r and the range for bucket b.<br>
<code>"p@v#q" @ b depends on "q$b" @ s</code></p>
</li>
<li>
<p>Dependencies of "q$b" are the same than q.</p>
</li>
</ul>
<p>Let's take a concrete example with the following dependencies:</p>
<div class="codehilite"><pre><span></span><code>root @ 1 depends on a * and d *
a @ 1 depends on
    b @ [2.1, 4.5[
    c @ [0.4, 0.6[
d @ 1 depends on b @ [1, 2[
b @ 1.0 has no dependency
b @ 2.1 has no dependency
b @ 3.0 has no dependency
c @ 0.4 has no dependency
c @ 0.5 has no dependency
</code></pre></div>
<p>The typical solution would be:<br>
<code>a @ 1, b @ 1.0, b @ 3.0, c @ 0.5, d @ 1, root @ 1</code></p>
<p>Let's precompute existing buckets for each package.<br>
There is only one bucket for each one of "root", "a" and "d" since those<br>
only have one existing version.<br>
Package "b" has buckets 1.0.0, 2.0.0 and 3.0.0.<br>
Package "c" has buckets 0.4.0 and 0.5.0.</p>
<p>So now let's see what are the dependencies that would be generated<br>
on the fly by a dependency provider with bucketted logic.</p>
<div class="codehilite"><pre><span></span><code>&quot;root&quot; @ 1.0.0 depends on &quot;root@1.0.0#a&quot; @ * and &quot;root@1.0.0#d&quot; @ *
&quot;root@1.0.0#a&quot; @ 1.0.0 depends on &quot;a$1.0.0&quot; @ [1.0.0,2.0.0[
&quot;root@1.0.0#d&quot; @ 1.0.0 depends on &quot;d$1.0.0&quot; @ [1.0.0,2.0.0[

&quot;a&quot; @ 1.0.0 depends on &quot;a@1.0.0#b&quot; @ * and &quot;a@1.0.0#c&quot; @ *
&quot;a@1.0.0#b&quot; @ 2.0.0 depends on &quot;b$2.0.0&quot; @ [2.1.0,3.0.0[
&quot;a@1.0.0#b&quot; @ 3.0.0 depends on &quot;b$3.0.0&quot; @ [3.0.0,4.0.0[
&quot;a@1.0.0#c&quot; @ 0.4.0 depends on &quot;c$0.4.0&quot; @ [0.4.0,0.5.0[
&quot;a@1.0.0#c&quot; @ 0.5.0 depends on &quot;c$0.5.0&quot; @ [0.5.0,0.6.0[

&quot;d&quot; @ 1.0.0 depends on &quot;d@1.0.0#b&quot; @ *
&quot;d@1.0.0#b&quot; @ 1.0.0 depends on &quot;b$1.0.0&quot; @ [1.0.0,2.0.0[
</code></pre></div>



<a name="217578928"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/crates.io%20index/near/217578928" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Eh2406 <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/crates.2Eio.20index.html#217578928">(Nov 23 2020 at 00:37)</a>:</h4>
<p>That makes sence and I think is what my implementation does.</p>



<a name="217586200"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/crates.io%20index/near/217586200" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Eh2406 <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/crates.2Eio.20index.html#217586200">(Nov 23 2020 at 03:33)</a>:</h4>
<p>Force pushed a change that uses a little of the nomenclature you suggested.</p>



<a name="239599653"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/crates.io%20index/near/239599653" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Eh2406 <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/crates.2Eio.20index.html#239599653">(May 20 2021 at 14:20)</a>:</h4>
<p>I just modified my script to run all versions of all packages, and it successfully ran! it took 21.6 hours and the resulting file is 1.17GB. The slowest case is <code>hobo</code> taking 571 seconds followed by lots of <code>solana-*</code> crates that take longer then 180 seconds. I have reason to believe that they would be helped by <a href="#narrow/stream/260232-t-cargo.2FPubGrub/topic/0.2E2.2Ex.20api.20is.20a.20Selection.20sort">https://rust-lang.zulipchat.com/#narrow/stream/260232-t-cargo.2FPubGrub/topic/0.2E2.2Ex.20api.20is.20a.20Selection.20sort</a> but have not measured by how much. This is amazingly good news, there are no cases in <a href="http://crates.io">crates.io</a> that triggers exponential blow up!</p>
<p>Perf is very sensitive to <code>P::Clone</code>, I had to use an arena to get things to run this fast and to avoid a stack overflow.</p>



<a name="239773900"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/crates.io%20index/near/239773900" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Matthieu Pizenberg <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/crates.2Eio.20index.html#239773900">(May 21 2021 at 16:00)</a>:</h4>
<p>Wow congrats! that is good new indeed!</p>



<hr><p>Last updated: Aug 07 2021 at 22:04 UTC</p>
</html>